CS154Spring 2013Lecture Notes
Formal Languages and Computability
Videos of lectures are available. As
they are on my office machine and I don't want robots to try to download them, the
directory is password protected. The login is guest and the password is guest.
Below are my lecture notes for the class so far.
They should serve as a rough guide to what was covered on any given day.
Frequently, however, I say more in class than is in these notes.
Also, I tend to dynamically correct typos on the board
that might appear in these lecture notes. So caveat emptor.
Week 1: [Jan. 23 -- Automata theory and Computability]
Week 2: [Jan. 28 -- Sets, Relations, Functions, Graphs]
[Jan. 30 -- Functions, Graphs, Trees, and Proofs]
Week 3: [Feb. 4 -- Finite Automata] [Feb. 6 -- More Deterministic Finite Automata]
Week 4: [Feb. 11 -- Nondeterministic Finite Automata] [Feb. 13 -- Minimization, Closure Proofs, Regular Expressions]
Week 5: [Feb. 18 -- Practice Midterm Day] [Feb. 20 -- Midterm 1]
Week 6: [Feb. 25 -- Regular Expressions and Grammars]
[Feb. 27 -- Homomorphism, Quotients, Pumping Lemma]
Week 7: [Mar. 4 -- Context Free Grammars] [Mar. 6 -- Transforming Grammars]
Week 8: [Mar. 11 -- Chomsky Normal Form] [Mar. 13 -- Push Down Automata]
Week 9: [Mar. 18 -- More PDAs, Pumping Lemma for CFGs, Compression]
[Mar. 20 -- CFL Closure Properties, CFL Algorithms, TMs]
Week 10: [Spring Break]
Week 11: [Apr. 1 -- Holiday] [Apr. 3 -- Building Bigger Machines From Smaller Ones]
Week 12: [Apr. 8 -- Practice Midterm Day] [Apr. 10 -- Midterm 2]
Week 13: [Apr. 15 -- Equivalence of Turing Machine Variants]
[Apr. 17 -- More Computational Variants]
Week 14: [Apr. 22 -- Nondeterministic TMs, Universal Turing Machines, Diagonalization]
[Apr. 24 -- Hierarchy Theorems, co-r.e. sets, Reductions]
Week 15: [Apr. 29 -- Computation Histories][May 1 -- PCP, Rice's Theorem]
Week 15: [May 6 -- The Recursion Theorem] [May 8 -- Komolgorov Complexity] |